﻿<?xml version="1.0" encoding="utf8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
               "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<title>高性能服务器设计</title>
<meta http-equiv="Content-Type" content="text/html;charset=utf8"/>
<meta name="title" content="高性能服务器设计"/>
<meta name="generator" content="Org-mode"/>
<meta name="generated" content="2015-07-10T12:07+0800"/>
<meta name="author" content=""/>
<meta name="description" content=""/>
<meta name="keywords" content=""/>
<style type="text/css">
 <!--/*--><![CDATA[/*><!--*/
  html { font-family: Times, serif; font-size: 12pt; }
  .title  { text-align: center; }
  .todo   { color: red; }
  .done   { color: green; }
  .tag    { background-color: #add8e6; font-weight:normal }
  .target { }
  .timestamp { color: #bebebe; }
  .timestamp-kwd { color: #5f9ea0; }
  .right  {margin-left:auto; margin-right:0px;  text-align:right;}
  .left   {margin-left:0px;  margin-right:auto; text-align:left;}
  .center {margin-left:auto; margin-right:auto; text-align:center;}
  p.verse { margin-left: 3% }
  pre {
	border: 1pt solid #AEBDCC;
	background-color: #F3F5F7;
	padding: 5pt;
	font-family: courier, monospace;
        font-size: 90%;
        overflow:auto;
  }
  table { border-collapse: collapse; }
  td, th { vertical-align: top;  }
  th.right  { text-align:center;  }
  th.left   { text-align:center;   }
  th.center { text-align:center; }
  td.right  { text-align:right;  }
  td.left   { text-align:left;   }
  td.center { text-align:center; }
  dt { font-weight: bold; }
  div.figure { padding: 0.5em; }
  div.figure p { text-align: center; }
  div.inlinetask {
    padding:10px;
    border:2px solid gray;
    margin:10px;
    background: #ffffcc;
  }
  textarea { overflow-x: auto; }
  .linenr { font-size:smaller }
  .code-highlighted {background-color:#ffff00;}
  .org-info-js_info-navigation { border-style:none; }
  #org-info-js_console-label { font-size:10px; font-weight:bold;
                               white-space:nowrap; }
  .org-info-js_search-highlight {background-color:#ffff00; color:#000000;
                                 font-weight:bold; }
  /*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart  The following is the entire license notice for the
JavaScript code in this tag.

Copyright (C) 2012-2013 Free Software Foundation, Inc.

The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version.  The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.  See the GNU GPL for more details.

As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.


@licend  The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
 function CodeHighlightOn(elem, id)
 {
   var target = document.getElementById(id);
   if(null != target) {
     elem.cacheClassElem = elem.className;
     elem.cacheClassTarget = target.className;
     target.className = "code-highlighted";
     elem.className   = "code-highlighted";
   }
 }
 function CodeHighlightOff(elem, id)
 {
   var target = document.getElementById(id);
   if(elem.cacheClassElem)
     elem.className = elem.cacheClassElem;
   if(elem.cacheClassTarget)
     target.className = elem.cacheClassTarget;
 }
/*]]>*///-->
</script>

</head>
<body>

<div id="preamble">

</div>

<div id="content">
<h1 class="title">高性能服务器设计</h1>


<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#sec-1">1 简介</a></li>
<li><a href="#sec-2">2 数据复制</a></li>
<li><a href="#sec-3">3 上下文切换</a></li>
<li><a href="#sec-4">4 内存分配</a></li>
<li><a href="#sec-5">5 锁竞争</a></li>
<li><a href="#sec-6">6 其它</a></li>
</ul>
</div>
</div>

<div id="outline-container-1" class="outline-2">
<h2 id="sec-1"><span class="section-number-2">1</span> 简介</h2>
<div class="outline-text-2" id="text-1">


<p>
本文档的目的是分享一些我做开发多年来如何开发一个"server"的想法。更精确地说，我将编写一类程序，这类程序被设计用来每秒处理大量分散的消息和请求。网络服务器通常符合这个定义，但不是所有的程序都是真正意义上的服务器。
</p>
<p>
本文将不会涉及并行应用，虽然在单个程序中多任务处理已经很常见。但并行并不会引入许多有趣的挑战。有趣的挑战是处理请求的基础设施成为整个性能的限制因素，所以改进基础设施实际上改进性能。
</p>
<p>
本文的剩余部分将以下面4个低性能的操作为中心：
</p><ol>
<li>数据复制(Data copies)
</li>
<li>上下文切换(Context switches)
</li>
<li>内存分配(Memory allocation)
</li>
<li>锁竞争(Lock contention)
</li>
</ol>

<p>本文最后还有一个章节，但这些才是最大的性能杀手。如果你能够处理大部分请求，不使用数据复制，不进行上下文切换，不使用内存分配器和不竞争锁，你将拥有一个性能良好的服务器，即使它有一些次要错误。
</p>
</div>

</div>

<div id="outline-container-2" class="outline-2">
<h2 id="sec-2"><span class="section-number-2">2</span> 数据复制</h2>
<div class="outline-text-2" id="text-2">


<p>
这可能是一个非常短小的章节，因为一部分人已经学过这一课。每个人都知道数据复制是不好的。
</p>
<p>
尽管数据复制的坏处很明显，但仍然有一部人会忽视它。数据复制往往是隐蔽和伪装的。你真的知道你调用的驱动和库中的代码是否存在数据复制？可能会超出你的想象。
</p>
<p>
避免数据复制的可靠准确的方法是间接使用buffer描述符(或buffer描述符chains)传递而不是单纯使用buffer指针。每个描述符通常由以下组成：
</p><ul>
<li>表示整个buffer的指针和长度
</li>
<li>表示buffer实际填充部分的指针和长度或偏移量和长度
</li>
<li>在一个列表中指向其它buffer描述符的前趋和后继指针
</li>
<li>一个引用计数器
</li>
</ul>

<p>现在，代码可以简单地在相应的buffer描述符上增加引用计数，而不是复制一段数据来确保这段数据保留在内存中。在某些情况下它能工作得很好，包含在一个典型网络协议栈的操作上，但它也可能变得非常让人头痛。一般而言，在chains的开头或结尾添加buffers，给整个buffers增加引用计数，一次释放整个chains都是很容易的。在chains中间添加buffers，一块一块释放buffers或引用buffer的一部分都会将变得困难。试图拆分和合并buffers简直会让你发疯。
</p>
<p>
我不推荐在所有情况下都使用这种方式。因为每次你想查看某个字段（数据）时都必须遍历描述符chains，这将非常痛苦。这比数据复制更糟糕。我发现这种方式最适合在程序中标识大对象，比如数据块，确保每个块都是如上所述单独分配，这样它们就不必进行复制。
</p>
<p>
最后关于数据复制的观点：不要过度的避免数据复制。我见过太多的代码，为了避免数据复制而结果反而变得更糟，就像强制上下文切换或产生大量I/O请求一样。数据复制的代价是昂贵的，当你在寻找哪些地方有冗余操作时，首先应该检查是数据复制。为了清除最终少量的数据复制而造成复杂度翻倍通常是浪费时间的，不如将时间花费在其它方面可能更好。
</p>
</div>

</div>

<div id="outline-container-3" class="outline-2">
<h2 id="sec-3"><span class="section-number-2">3</span> 上下文切换</h2>
<div class="outline-text-2" id="text-3">


<p>
相对每个都知道数据复制的坏处是很明显的，但经常让我感到惊讶是非常的人忽视了上下文切换对性能的影响。据我的经验，在高负载的情况下上下文切换背后的"灾难"比数据复制更多。系统开始花费更多的时间从一个线程切换到另一个，而不是做真正有用的工作。令人惊讶的是，在某种情况下，引起过多的上下文切换的原因非常明显。上下文切换的第1个原因是活跃的线程数超过了处理器数。活跃线程与处理器的比例增加，上下文切换的次数也会增加（通常呈指数形式）。这个非常简单的事实解释了为什么每个连接一个线程的多线程设计伸缩性非常差。一个可伸缩系统的唯一现实选择是限制活跃纯程的数量少于或等于处理器数量。这种方式的一个流行变种是永远仅仅只使用一个线程；虽然这种方式避免了上下文抖动和锁的需求，但它也不能实现多处理器的吞吐量的价值。
</p>
<p>
一个"thread-frugal"的程序首要事件是解决如何使一个线程同时处理多个连接。这通常意味着在前端使用select/poll，异步I/O，信号和completion ports，在其背后使用一个事件驱动结构。在这个方面Dan Kegel的<a href="http://www.kegel.com/c10k.html"> C10K </a>论文是一个很好的资源。就自己而言，我认为select/poll和信号是丑陋的，因此我更喜欢AIO或completion ports，但实际上这并不重要。
</p>
<p>
一个多线程事件驱动服务器的最简单概念模型在它的中心有一个队列。请求由一个或多个"监听线程读取，并将其放入队列，一个或多个"工作"线程从队列中移出请求并处理它们。从概念上讲，这是一个好的模型，实际上大部人经常使用这个方式来实现他们的代码。为什么这样不对呢？因为引起上下文切换的第2个原因将工作从一个线程转移到另一个线程。有些人甚至错上加错地要求使用最初的线程来发送请求的响应 - 每次请求至导致2次上下文切换。使用一种"对称"方式是非常重要的，一个给定线程能够从监听线程变成工作者线程，再变成监听线程，甚至没有上下文改变。不管它是否涉及在线程之间分割连接还是将所有线程都成为监听线程的问题似乎不重要了。
</p>
<p>
通常，是不可能知道下一时刻有多少线程是活跃的。毕竟，连接上的请求可能在任何时刻到达，或专注于各种维护任务的"后台"线程可能随时被唤醒。如果你不知道有多少个线程是活跃的，你怎么能限制活跃的数量呢？以我的经验，最有效也是最简单的方式之一：使用老式计数信号量，每个线程每当做"真正工作"时必须执有该信号量。如果已经到达了线程限制，每个监听模式的线程可能引发一个额外的上下文切换，因为它在信号量上唤醒，然后阻塞。一旦所有监听模式的线程都阻塞，它们将不会继续争夺资源直到某个线程"释放信号"。更重要的是，这种方式处理维护进程 - 维护进程大部时间在睡眠 - 比大多数方式更优雅。
</p>
<p>
曾经请求的处理被划分为两个阶段（监听者和工作者），用多个线程来服务这些阶段。将来甚至可能将处理划分更多的阶段是件很自然的事。在最简单的形式中，处理一个请求因此变成了一个在一个方向相继调用阶段的事情。然而，事件可能变得更复杂；一个阶段可能是两条涉及不同阶段的处理路径的交叉点，或者它可能产生一个回复(例如，一个缓存的值）而不调用下一步的阶段。因此，每个阶段需要能够为请求指明"下一步应该发生什么"。通过阶段调度函数的返回值来表示三个可能性：
</p><ul>
<li>请求需要被传递给另一个阶段(返回值可能是ID或指针)
</li>
<li>请求已经完成(一个特殊"请求完成"的返回值)
</li>
<li>请求被阻塞(一个特殊"请求阻塞"的返回值)。和前面情况一样，除了请求不会被释放，随后其它线程继续执行。
</li>
</ul>

<p>注意，在这个模型中，请求的排列是阶段内部完成，而不是阶段之间。这个避免将一个请求放到后继阶段的列队中，然后立即调用后继阶段，并且再将请求出队。这种大量队列活动和锁操作是毫无意义的。
</p>
<p>
将一个复杂的任务拆分成多个更小的相互协作的部分似乎很熟悉，那是因为这实际上已经非常老了。我的方法的根源来自于由C.A.R Hoared在1978年阐述的<a href="http://www.afm.sbu.ac.uk/csp/"> 通信序列化进程</a> （CSP）思想，进而可以追溯回到1963年由Per Brinch Hansen和Matthew Conway提交的思想。然而，当Hoara创建CSP术语时，"process"是从抽象数学观念而言的。一个CSP process与操作系统的同名实体（进程）没有关系。在我看来，实现CSP的常见方法是通过在单个OS线程中的协程为用户提供不具有伸缩性的并发。
</p>
<p>
在一个理智方向上进化的阶段式执行（staged-execution)思想的一个现代实例是Matt Wlsh的<a href="http://www.afm.sbu.ac.uk/csp/">SEDA </a>.实事上，SEDA正是一个"server architecture done right"的好示例，在一些特有的特征上值得讨论（特别是与我上面提到的那些不同的地方）：
</p><ol>
<li>SEDA的"批处理"倾向于强调一次一个阶段处理多个请求，而我的方法倾向于强调一次通过多个阶段处理单个请求。
</li>
<li>SEDA的一个重要的缺陷，在我看来，它为每个阶段分配了一个单独的线程池。因此，上面提到的上下文切换的2个原因仍然存在。
</li>
<li>在学术研究项目环境中，用Java实现的SEDA可能有意义。但在真实的世界中，我认为这个选择是不好的。
</li>
</ol>


</div>

</div>

<div id="outline-container-4" class="outline-2">
<h2 id="sec-4"><span class="section-number-2">4</span> 内存分配</h2>
<div class="outline-text-2" id="text-4">


<p>
在许多应用中，分配和释放内存是最常见的操作之一。因此，为了构建一个更高效的通用内存分配器，许多聪明的技巧被开发出来。然而，再多的聪明也不能弥补这样的内存分配器在许多情况下不可避免地比原有的效率低。因此我有关于如何避免使用系统内存分配器的三个建议。
</p>
<p>
建议1是使用预分配。我们知道静态分配是不好的，它在程序功能上强加人为限制，但有许多其它形式的预分配是相当有利的。通常原因归结于一个事实：一次系统内存分配与多次要好，即使在进程中一些内存被浪费。因此，如果能够断言一次从来不会使用超过N个项内存分配，在程序启动时预分可能是有效的选择。即使不是这种情况，在刚开始为一个请求处理程序预分配好一切比在需要时才按分配每块内存要好。此外通过系统分配器一次分配多个连续的内存是可能的，这往往大大简化错误恢复的代码。如果内存非常紧张，预分配可能不是一个好的选择。除了非常极端情况，通常预分配是稳赢的选择。
</p>
<p>
建立2是为频繁分配和释放的对象使用后备列表(lookaside lists)。基本思想是把最近释放的对象放入一个列表而不是真的释放它们，希望它们尽可能快的再次被使用，仅仅只需要从列表中取出而不是从系统内存中分配。一个额外的好处，从后备列表中移进或取出，可以跳过复杂对象初始化和析构。
</p>
<p>
让后备列表不加限制的增长通常是不可取的，因为即使你的程序空闲的也从不会真正释放任何内存。因此，使用某种周期性"清洁"的任务来释放不活跃的对象通常是必要的。如果清洁引入了不适当的复杂度和锁竞争，它将是不可取的。一个比较好的妥协方法是一个后备列表实际上由两个独立上锁的"old"和"new"列表组成。优先从new列表中分配，之后从old列表中分配，最后才从系统分配。对象总是被释放到new列表中。清洁工线程操作如下：
</p><ol>
<li>将两个列表上锁
</li>
<li>保存old列表的头部
</li>
<li>将(先前的)new列表赋值给old列表
</li>
<li>解锁
</li>
<li>在空闲时释放已保存的old列表中所有对象
</li>
</ol>

<p>这种类型系统中的对象只有在不需要时才会真正释放，至少经过一个完整的清洁时间间隔，但总是不到2个时间间隔。最重要的是，清洁线程在执行它的任务时不会与正规线程竞争任何锁。从原理上讲，同样的方式也可推广到两个以上的阶段中，但我没有发现那有用。
</p>
<p>
建议3是与锁的处理有关，我们还没有讨论，我先抛开不说。锁竞争在内存分配中经常是最大开销，甚至当后备列表在使用时。一个解决方案是维护多个私有的后备列表，这样任何一个列表都不会产生竞争。例如，你可以每个线程都有一个独立的后备列表。因此缓存的原因，每个处理器一个列表甚至可以更好，但只有在线程不被抢占的情况有用。为了创建一个非常低分配开销的系统，必须时甚至可以将私有后备列表与共享列表进行组合。
</p>
</div>

</div>

<div id="outline-container-5" class="outline-2">
<h2 id="sec-5"><span class="section-number-2">5</span> 锁竞争</h2>
<div class="outline-text-2" id="text-5">


<p>
高效锁方案是出了名地难以设计。我把它称为Scylla和Charybdis。Scylla是一个简单粗粒度的锁，在并行中可能会发生活动串行化，因此牺牲了性能和可伸缩性；Charybdis是相当复杂细粒度的锁，锁所占用的空间和锁操作花费的时间会消弱性能。Scylla附近浅滩表示死锁和活锁的条件；Charybdis附近浅滩表示竞争条件。在它们之间，有一个狭窄的海峡表示锁的有效性和正确性&hellip;还在那里吗？由于锁往往与程序逻辑紧密相连，如果没有从根本上了解程序是如何工作的，想要设计一个好的锁方案是不可能的。这就是为什么人们讨厌锁，并试图让非扩展单一线程的方式的使用合理化。
</p>
<p>
几乎每个锁方案都始于"一把大锁锁住一切"，并且寄希望于性能不会被影响。当希望破灭时（几乎总是），大锁分解多个小锁，并且继续祷告，然后整个过程继续重复，大概直到性能是满足的。但是通常情况下，每次迭代会增加20%~50%的复杂度和锁开销以换取降低5%~10%的锁竞争。如果幸运，最终结果是性能仍然有适度增长，但是实际上性能降低并不少见。
</p>
<p>
在我看来，事情变得更糟是因为上面提到的方法从根本上是错误的。把"解决方案"想像成一座山脉，山峰表示好的方案，山谷表示不好的方案。问题是"一把大锁"的起点几乎总是与高峰之间被各种山谷，小山和死胡同分隔开。这是一个典型的爬山问题。试图仅仅只通过小碎步从这个的起点到达高峰，并且从不走下坡路是几乎不可能的。需要一个从根本上不同的方式来接近山峰。
</p>
<p>
你必须做的第一件事是构建一张锁的图。这个图有两个坐标轴：
</p><ul>
<li>纵坐标代表代码。如果你使用一个非分支阶段的架构，你可能已经有一份展示分层的图表，像OSI模型网络协议栈
</li>
<li>横坐标代表数据。在每个阶段，每个请求都被赋予了与自己资源相关的数据集。
</li>
</ul>

<p>现你有了一张表格，每个单元格代表在一个特定处理阶段中的一个特定数据。最重要的是以下规则：两个请求不应该竞争除非它们有相同的数据集和相同的处理阶段。如果你能做到这些，你已经成功了一半。
</p>
<p>
一旦你定义好了表格，程序中的每个类型的锁都能够被绘制出来，接下来的目标就是确保绘制的锁点尽可能的均匀分布在两轴之间。遗憾的是，这部分与应用是相关的。你必须像一个砖石切割者一样思考，使用你的知识找到程序中阶段与数据集之间自然的"分裂线"。有时它们是显而易见的。有时它们很难找到，但在回顾
过程中它们似乎会更明显。将代码分成阶段是一个复杂的程序设计问题，所以这里我没有什么可提供的，但有一些关于如何定义数据集的建议：
</p><ul>
<li>如果你有某种块编号或hash或事务ID与请求关联，你可以通过数据集的编号来区分这些数据
</li>
<li>有时，动态地为请求分配数据集，基于哪些数据集拥有大多数可用资源比基于请求的某些固有属性要好。
</li>
<li>确保每个阶段的数据集分配都是不同的，这经常会是有用的。以便保证请求在一个阶段将不会出现竞争。
</li>
</ul>

<p>如果你从纵向和横向分开你的"锁空间"，确信锁活动是均匀分散在单元络中，你可以很确定你的锁处于非常良好的状态。不过，还有一步。你还记得之前的"小碎步"的方式吗？它仍然存在，现在你在一个更好的起点。用比喻的术语你可能已经到达了山脉最高峰的斜坡了，但可能还不是山峰。现在是时候来收集竞争统计数据和看看你需要如何改进，使用不同方式拆分阶段和数据集，然后收集更多的统计数据直到你满意为止。如果你完成这些，你肯定能从山顶看到一个好风景。
</p>
</div>

</div>

<div id="outline-container-6" class="outline-2">
<h2 id="sec-6"><span class="section-number-2">6</span> 其它</h2>
<div class="outline-text-2" id="text-6">


<p>
我已经介绍了在服务器设计中的4个最大性能问题。但对于任意特定服务器，仍然还有一些重要的问题需要指出。大部分源于你的平台/环境：
</p><ul>
<li>你的存储子系统在大量或少量请求情况下是如何执行的？使用顺序还是随机？预读和延迟写的工作表现如何？
</li>
<li>你使用的网络协议效率如何？你能够设置的参数或标志是否使它表现更好？为了避免小报文，你是否使用了像TCP<sub>CORK，MSG</sub><sub>PUSH或Nagle</sub>-toggling这样的技巧。
</li>
<li>你的系统是否支持scatter/gather I/O(例如，readv/writev)?使用这些可以改进性能，同时也可以减轻使用buffer chains的痛苦。
</li>
<li>你的page大小是多少？你的cache-line大小是多少？边界对齐是否值的？相比其它事情，系统调用或上下文开销有多大？
</li>
<li>你的reader/writer锁会饥饿吗？你的事件是否有"惊群"问题？你的sleep/wakeup是否是是糟糕的行为，当X唤醒Y时一个Y的上文切换立即发生甚至X仍然来有事要做？
</li>
</ul>

<p>我确信我可以考虑更多的问题。在任何特殊情况下，上面的这些问题可能都不值得去做，但至少思考它们通常是值得的。你如果你不知道答案 - 其中许多你将在系统文档中找不到 - 去查明。编写一个测试程序或微型基准测试来找到答案。编写这样的代码本身也一个有用的技能。如果你编写的代码运行多个平台上，你应该将每个平台的功能抽象到库中，这样你能够提升一个平台性能支持特定功能。
</p>
<p>
"知其所以然"对于自己的代码也适用。找出你代码中有哪些重要高级操作，在不同条件它们的耗时。这与传统分析不同，它是关于设计元素的测量，不是具体实现。低级优化通常是那些搞砸了设计的人的最后手段。
</p></div>
</div>
</div>

<div id="postamble">
<p class="date">Date: 2015-07-10T12:07+0800</p>
<p class="author">Author: </p>
<p class="creator"><a href="http://orgmode.org">Org</a> version 7.9.3f with <a href="http://www.gnu.org/software/emacs/">Emacs</a> version 24</p>
<a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a>

</div>
</body>
</html>
